package com.nine.face.sort;

import java.util.Arrays;

/**
 * 双边循环
 */
public class QuickSort2 {

    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        //partition(a, 0, a.length - 1);
        quick(a, 0, a.length - 1);
    }

    // 提供递归方法
    private static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        // 一趟快速排序，返回基准点索引
        int p = partition(a, l, h);
        // 左边分区范围
        quick(a, l, p - 1);
        // 右边分区范围
        quick(a, p + 1, h);
    }

    /**
     * @return 返回值代表基准点元素所在的正确索引，用它来确定下一轮分区的边界
     */
    private static int partition(int[] a, int l, int h) {
        int pv = a[l];
        int i = l;
        int j = h;
        while (i < j) {
            // 注意：顺序不能变，需要先处理 j，然后处理 i，否则会出错
            // 注意：内层循环，必须也要加上 i< j 的条件，否则会越界
            // j 从右找小的
            while (i < j && a[j] > pv) {
                j--;
            }
            // 注意：一定要是小于等于，避免基准点元素被错误交换
            // i 从左找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            swap(a, i, j);
        }
        // 基准点放到中间
        swap(a, i, l);
        System.out.println(Arrays.toString(a));
        return i;
    }

    // 交换数组元素
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
